package 面试题17_打印从1到最大的n位数.递归实现全排列;

import org.junit.Test;

import java.util.ArrayList;
import java.util.List;

/**
 * @Author ：xu_xiaofeng.
 * @Date ：Created in 19:58 2021/2/15
 * @Description：
 */
public class Solution {
    //    public int[] printNumbers(int n) {
//
//    }

    private List<char[]> list;
    private char[] number;

    private char[] loop = {'0', '1', '2', '3', '4', '5', '6', '7', '8', '9'};

    public int[] printNumbers(int n) {

        // 特殊输入
//        if (n <= 0) {
//            return new int[0];
//        }

        list = new ArrayList<>();

        number = new char[n];

        dfs(0, n);

        int[] res = new int[list.size() - 1];

        for (int i = 1; i < list.size(); i++) {
            res[i - 1] = string2Int(list.get(i));
        }

        return res;
    }

    /**
     * @param index 位数索引，从高位到低位
     */
    void dfs(int index, int length) {
        // 递归结束条件，处理到最后一位（个位）
        if (index == length - 1) {

            for (int i = 0; i < 10; i++) {
                number[index] = loop[i];
                list.add(number.clone());
            }

            return;
        }

        // 从0开始遍历当前位的下一位（如，当前位是百，则下一位是十）
        for (int i = 0; i < 10; i++) {
            // 设置当前位的值
            number[index] = loop[i];

            // 处理下一位
            dfs(index + 1, length);

        }
    }

    private int string2Int(char[] num) {
        StringBuilder sb = new StringBuilder();

        for (int i = 0; i < num.length; i++) {
            sb.append(num[i]);
        }

        int res = Integer.parseInt(sb.toString());

        return res;
    }

    @Test
    public void test() {
        printNumbers(2);

        for (char[] num : list) {
            for (int i = 0; i < num.length; i++) {
                System.out.print(num[i]);
            }
            System.out.print('\n');
        }

        System.out.println(list.size());
    }
}
